package class02;

import java.util.PriorityQueue;

public class Code04_SortArrayDistanceLessK {

	public void sortedArrDistanceLessK(int[] arr, int k) {
		//默认小根堆
		PriorityQueue<Integer> heap = new PriorityQueue<>();
		int index = 0;

		//把下标为0到k的前k+1个数字放入小根堆
		for (; index <= Math.min(arr.length, k); index++) {
			heap.add(arr[index]);
		}

		int i = 0;
		for (; index < arr.length; i++, index++) {
			heap.add(arr[index]); //把index后面的放入小根堆？？？？这里是不是因为index的初始值问题啊
			arr[i] = heap.poll(); //弹出小根堆最小值
		}
		while (!heap.isEmpty()) {
			arr[i++] = heap.poll();
		}
	}


	public static void main(String[] args) {
		//扩容每次扩容2倍
		PriorityQueue<Integer> heap = new PriorityQueue<>();

		heap.add(4);
		heap.add(8);
		heap.add(3);
		heap.add(5);
		heap.add(2);
		heap.add(1);

		while (!heap.isEmpty()){
			System.out.println(heap.poll());
		}
	}

}
